/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-11-08
 * Time: 10:16
 */
public class ZeroOneKnapsack {

    // 基础二维DP解法
    public static int knapsackBasic(int[] weights, int[] values, int W) {
        int n = weights.length;
        if (n == 0 || W == 0) return 0;

        // dp[i][w]：前i个物品，承重≤w的最大价值
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) { // 遍历物品
            for (int w = 1; w <= W; w++) { // 遍历承重
                // 不选第i个物品（i-1是实际索引）
                dp[i][w] = dp[i - 1][w];
                // 若当前物品重量≤承重，考虑选它的情况
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w],
                            dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[n][W];
    }

    // 空间优化：一维DP解法（推荐，节省空间）
    public static int knapsackOptimized(int[] weights, int[] values, int W) {
        int n = weights.length;
        if (n == 0 || W == 0) return 0;

        // dp[w]：承重≤w的最大价值（仅用一维数组）
        int[] dp = new int[W + 1];

        for (int i = 0; i < n; i++) { // 遍历每个物品
            // 从后往前更新，避免覆盖上一行的有用数据
            for (int w = W; w >= weights[i]; w--) {
                // 选当前物品 vs 不选，取最大值
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        // 测试用例：物品重量、价值、背包承重
        int[] weights = {2, 3, 4, 5}; // 物品重量
        int[] values = {3, 4, 5, 6};  // 对应价值
        int W = 8;                    // 背包最大承重

        // 基础解法
        int maxValue1 = knapsackBasic(weights, values, W);
        System.out.println("基础二维DP解法最大价值：" + maxValue1); // 输出：10（选重量3+5，价值4+6）

        // 优化解法
        int maxValue2 = knapsackOptimized(weights, values, W);
        System.out.println("一维DP优化解法最大价值：" + maxValue2); // 输出：10
    }
}